| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 128 MB | 94366 | 22036 | 16592 | 21.508% |
[백준] 1244번: 스위치 켜고 끄기
문제
1부터 연속적으로 번호가 붙어있는 스위치들이 있다. 스위치는 켜져 있거나 꺼져있는 상태이다. <그림 1>에 스위치 8개의 상태가 표시되어 있다. ‘1’은 스위치가 켜져 있음을, ‘0’은 꺼져 있음을 나타낸다. 그리고 학생 몇 명을 뽑아서, 학생들에게 1 이상이고 스위치 개수 이하인 자연수를 하나씩 나누어주었다. 학생들은 자신의 성별과 받은 수에 따라 아래와 같은 방식으로 스위치를 조작하게 된다.
남학생은 스위치 번호가 자기가 받은 수의 배수이면, 그 스위치의 상태를 바꾼다. 즉, 스위치가 켜져 있으면 끄고, 꺼져 있으면 켠다. <그림 1>과 같은 상태에서 남학생이 3을 받았다면, 이 학생은 <그림 2>와 같이 3번, 6번 스위치의 상태를 바꾼다.
여학생은 자기가 받은 수와 같은 번호가 붙은 스위치를 중심으로 좌우가 대칭이면서 가장 많은 스위치를 포함하는 구간을 찾아서, 그 구간에 속한 스위치의 상태를 모두 바꾼다. 이때 구간에 속한 스위치 개수는 항상 홀수가 된다.
| 스위치 번호 | ① | ② | ③ | ④ | ⑤ | ⑥ | ⑦ | ⑧ |
|---|---|---|---|---|---|---|---|---|
| 스위치 상태 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 |
<그림 1>
예를 들어 <그림 2>에서 여학생이 3을 받았다면, 3번 스위치를 중심으로 2번, 4번 스위치의 상태가 같고 1번, 5번 스위치의 상태가 같으므로, <그림 3>과 같이 1번부터 5번까지 스위치의 상태를 모두 바꾼다. 만약 <그림 2>에서 여학생이 4를 받았다면, 3번, 5번 스위치의 상태가 서로 다르므로 4번 스위치의 상태만 바꾼다.
| 스위치 번호 | ① | ② | ③ | ④ | ⑤ | ⑥ | ⑦ | ⑧ |
|---|---|---|---|---|---|---|---|---|
| 스위치 상태 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 |
<그림 2>
| 스위치 번호 | ① | ② | ③ | ④ | ⑤ | ⑥ | ⑦ | ⑧ |
|---|---|---|---|---|---|---|---|---|
| 스위치 상태 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
<그림 3>
입력으로 스위치들의 처음 상태가 주어지고, 각 학생의 성별과 받은 수가 주어진다. 학생들은 입력되는 순서대로 자기의 성별과 받은 수에 따라 스위치의 상태를 바꾸었을 때, 스위치들의 마지막 상태를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 스위치 개수가 주어진다. 스위치 개수는 100 이하인 양의 정수이다. 둘째 줄에는 각 스위치의 상태가 주어진다. 켜져 있으면 1, 꺼져있으면 0이라고 표시하고 사이에 빈칸이 하나씩 있다. 셋째 줄에는 학생수가 주어진다. 학생수는 100 이하인 양의 정수이다. 넷째 줄부터 마지막 줄까지 한 줄에 한 학생의 성별, 학생이 받은 수가 주어진다. 남학생은 1로, 여학생은 2로 표시하고, 학생이 받은 수는 스위치 개수 이하인 양의 정수이다. 학생의 성별과 받은 수 사이에 빈칸이 하나씩 있다.
출력
스위치의 상태를 1번 스위치에서 시작하여 마지막 스위치까지 한 줄에 20개씩 출력한다. 예를 들어 21번 스위치가 있다면 이 스위치의 상태는 둘째 줄 맨 앞에 출력한다. 켜진 스위치는 1, 꺼진 스위치는 0으로 표시하고, 스위치 상태 사이에 빈칸을 하나씩 둔다.
예제 입력 1
8
0 1 0 1 0 0 0 1
2
1 3
2 3
예제 출력 1
1 0 0 0 1 1 0 1
출처
- Olympiad > 한국정보올림피아드 > KOI 2000 > 초등부 2번
알고리즘 분류
- 구현
- 시뮬레이션
풀이
말 그대로 써 주면 된다. 그러나 여학생이 어떻게 스위치를 끄는지에서 중앙을 중심으로 어떻게 나아갈지에 대해 당연히 헷갈릴 수밖에 없다. 모든 조건을 깔끔하게 정리해 쓸 필요는 없다. 조건을 벗어나는 지점을 잡은 후 그 때에 더 이상 스위치를 끄거나 하지 못하게 막아 주면 된다.
스위치를 키고 끄는 반복문 부분에서 아래와 같이 해 주면 된다.
for(int i = 1; i < switch_len; i++) {
// calculates center.
// calculates left and right.
int left = center - i;
int right = center + i;
if(
(left < 0)
|| (right >= switch_len)
) break;
// 후략...
}
마찬가지로 주의해야 할 것은 20글자씩 끊는 것이다. 결과 스위치의 인덱스 나머지를 통한 접근을 생각해 냈다면 이것을 주의하자.
아래와 같이 (i != 0) 조건을 검사해야 한다.
이것을 하지 않으면 첫 줄에 개행이 끼어서 정답을 맞출 수 없다.
for(int i = 0; i < switch_len; i++) {
if(!(i%20) && (i != 0)) printf("%c", '\n');
printf((i%20) == 19? "%d":"%d ",switch_status[i]);
}
코드
#include <stdio.h>
int main() {
// read switch len, switch_len <= 100, assigning int(int, 32-bit, signed) since index defaults to int
int switch_len;
scanf("%d", &switch_len);
// read switch status
// input form distinguishes each button with ' '
// e.g,. 0 0 1 0 1 1 1
int switch_status[switch_len];
for(int i = 0; i < switch_len; i++) {
scanf("%d", &switch_status[i]);
}
// scan population
int popluation_of_students;
scanf("%d", &popluation_of_students);
// retrieve & immediately handle via for loop
for(int i = 0; i < popluation_of_students; i++) {
int sex, nr;
scanf("%d%d", &sex, &nr);
// if a student is Male
if(sex == 1) {
for(int i = 0; i < switch_len; i++) {
// if switch_nr % given_nr == 0
if(!((i+1) % nr)) {
switch_status[i] = !switch_status[i]; // using logical NOT
}
}
}
// if a student is Female
else if(sex == 2) {
int center = nr - 1;
// toggles center outside of for loop, left index, right index, center are all same.
switch_status[center] = !switch_status[center];
for(int i = 1; i < switch_len; i++) {
// calculates center.
// calculates left and right.
int left = center - i;
int right = center + i;
if(
(left < 0)
|| (right >= switch_len)
) break;
// if leftward status == rightward status, toggle
if(switch_status[left] == switch_status[right]) {
switch_status[left] = !switch_status[left] ; // using logical NOT
switch_status[right] = !switch_status[right]; // using logical NOT
} else {
break;
}
}
}
}
// Print each switches from 1 to last
// i == actual_switch_nr - 1
for(int i = 0; i < switch_len; i++) {
if(!(i%20) && (i != 0)) printf("%c", '\n');
printf((i%20) == 19? "%d":"%d ",switch_status[i]);
}
return 0;
}
결론
코딩 테스트에서 마지막 줄의 추가 개행 정도는 보통 봐 주지만, 첫 줄의 추가 개행을 봐 주지 않는다. 또한 조건이 복잡할 시 반복문 검사에서 다 해내려고 하지 말고 일부를 그 안에서 검사 후 빠져나오게 하자. 특히 이것이 범위에 대한 검사라면 반복문 안에서 검사하는 것이 끝까지 범위를 명시적으로 훑을 수 있기 때문에 주의해야 한다.